package com.sicheng.lc.周赛.分类.哈西表or计数or滑动窗口or双指针.双指针;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/9 20:57
 */
public class 替换后的最长重复字符 {
    //https://leetcode.cn/problems/longest-repeating-character-replacement/
    public int characterReplacement(String s, int k) {
        int l = 0;
        int[] cnt = new int[26];
        int max = 0;
        for (int r = 0; r < s.length(); r++) {
            int ch = s.charAt(r) - 'A';
            cnt[ch]++;
            while (!check(cnt, k)) {
                cnt[s.charAt(l) - 'A']--;
                l++;
            }
            max = Math.max(max, r - l + 1);
        }
        return max;
    }

    private boolean check(int[] cnt, int k) {
        int sum = 0, count = 0;
        for (int i : cnt) {
            sum += i;
            count = Math.max(count, i);
        }
        return sum - count <= k;
    }
}
